package main.java.com.itlin.recursion;

import java.util.Arrays;

public class E06Fibonacci {

    public static int fibonacci(int n) {
        int[] cache = new int[n + 1];
        Arrays.fill(cache, -1);//填充数组
        cache[0] = 0;
        cache[1] = 1;

        return f(n , cache);

    }
    public static int f(int n, int[] cache) {
        if (cache[n] != -1) return cache[n];
        int res =  f(n - 1, cache) + f(n - 2, cache);
        cache[n] = res;//存入数组

        return res;
    }

    public static long sum(long n) {
        if (n == 1) return 1;
        return sum(n - 1) + n;
    }

    public static void main(String[] args) {
        System.out.println(fibonacci(8));
        System.out.println(sum(1000));
    }
}
